1. Field of the Invention
The present invention relates to a method of an inverse transform between a spatial domain and a frequency domain, and in particular to a low-complexity inverse transform computation method capable of reducing the enormous computation amount and computation time required in a 2-Dimension (2-D) inverse transform, such that it is applicable to various video decoders.
2. The Prior Arts
With the advent of digital age, most of analog signals are required to be transformed into digital signals in data transmission and processing. However, due to the enormous quantity of data involved, therefore, quite a lot of researches are concentrated on data compression. For example, original multimedia data received by a multimedia device can not be handled and processed efficiently due to the enormous data quantity, limited memory storage capacity and bandwidth of the transmission channel. Therefore, many research institutions explore various multimedia data compression mechanisms, such that the compressed data can be transmitted through a transmission channel efficiently, or memory storage capacity required can be reduced effectively.
Though the compressed data are advantageous to data transmission and storage, yet in application of compressed data, it must be de-compressed and be restored to the original data format. However, decompression of data requires enormous amount of computations. By way of example, in decompression of the compressed video streams, various decoding operations must be performed, such as variable length decoding, de-quantification, inverse transform, and motion compensation. Wherein, the computational complexity of the inverse transform is quite large, and it requires a certain amount of computation time, yet video decompression requires fast and correct decoding, so that many researches have been concentrated on fast inverse transforms, and thereby the video decoder may perform real-time decoding.
In performing video or still image compression, data transformations between a spatial domain and a frequency domain are frequently utilized, such as discrete cosine transform or integer transform, etc., so that image frame data are transformed from the original spatial domain to the frequency domain, and after such a transform, the frequency-domain coefficients are concentrated in the low-frequency region, to be advantageous for the subsequent quantization processing and variable length coding. As to the de-compression process, the frame data are transformed from the original frequency domain to the spatial domain, such as Inverse Discrete Cosine Transform (IDCT) or Inverse Integer Transform (IIT). In these coefficient transforms between a spatial domain and a frequency domain, both coding and decoding require enormous computation amount. In a decoding process where fast speed is essential, the inverse transform process will overburden the decoder. Therefore, quite a lot of researches place their emphases on the fast computation topologies of inverse transforms, so as to reduce computational complexity and computation time. In general, a 2-D inverse transform operation can be expressed as the following equation (1):XN×N=DN×NT×YN×N×DN×N  (1)wherein, YN×N and XN×N represent respectively frequency-domain coefficients and spatial-domain coefficients. Additionally, DN×NT and DN×N are inverse transform matrices. In the MPEG-2 standard, N=8, and its coefficients of transform matrix are as shown in the following equation (2):
                              D                      8            ×            8                    T                =                              1            2                    ×                      [                                                                                1                                          2                                                                                                            cos                    ⁢                                          π                      16                                                                                                            cos                    ⁢                                          π                      8                                                                                                            cos                    ⁢                                                                  3                        ⁢                        π                                            16                                                                                                            1                                          2                                                                                                            sin                    ⁢                                                                  3                        ⁢                        π                                            16                                                                                                            sin                    ⁢                                          π                      8                                                                                                            sin                    ⁢                                          π                      16                                                                                                                                        1                                          2                                                                                                            cos                    ⁢                                                                  3                        ⁢                        π                                            16                                                                                                            sin                    ⁢                                          π                      8                                                                                                                                  -                      sin                                        ⁢                                          π                      16                                                                                                            -                                          1                                              2                                                                                                                                                        -                      cos                                        ⁢                                          π                      16                                                                                                                                  -                      cos                                        ⁢                                          π                      8                                                                                                                                  -                      sin                                        ⁢                                                                  3                        ⁢                        π                                            16                                                                                                                                        1                                          2                                                                                                            sin                    ⁢                                                                  3                        ⁢                        π                                            16                                                                                                                                  -                      sin                                        ⁢                                          π                      8                                                                                                                                  -                      cos                                        ⁢                                          π                      16                                                                                                            -                                          1                                              2                                                                                                                                  sin                    ⁢                                          π                      16                                                                                                            cos                    ⁢                                          π                      8                                                                                                            cos                    ⁢                                                                  3                        ⁢                        π                                            16                                                                                                                                        1                                          2                                                                                                            sin                    ⁢                                          π                      16                                                                                                                                  -                      cos                                        ⁢                                          π                      8                                                                                                                                  -                      sin                                        ⁢                                                                  3                        ⁢                        π                                            16                                                                                                            1                                          2                                                                                                            cos                    ⁢                                                                  3                        ⁢                        π                                            16                                                                                                                                  -                      sin                                        ⁢                                          π                      8                                                                                                                                  -                      cos                                        ⁢                                          π                      16                                                                                                                                        1                                          2                                                                                                                                  -                      sin                                        ⁢                                          π                      16                                                                                                                                  -                      cos                                        ⁢                                          π                      8                                                                                                            sin                    ⁢                                                                  3                        ⁢                        π                                            16                                                                                                            1                                          2                                                                                                                                  -                      cos                                        ⁢                                                                  3                        ⁢                        π                                            16                                                                                                                                  -                      sin                                        ⁢                                          π                      8                                                                                                            cos                    ⁢                                          π                      16                                                                                                                                        1                                          2                                                                                                                                  -                      sin                                        ⁢                                                                  3                        ⁢                        π                                            16                                                                                                                                  -                      sin                                        ⁢                                          π                      8                                                                                                            cos                    ⁢                                          π                      16                                                                                                            -                                          1                                              2                                                                                                                                                        -                      sin                                        ⁢                                          π                      16                                                                                                            cos                    ⁢                                          π                      8                                                                                                                                  -                      cos                                        ⁢                                                                  3                        ⁢                        π                                            16                                                                                                                                        1                                          2                                                                                                                                  -                      cos                                        ⁢                                                                  3                        ⁢                        π                                            16                                                                                                            sin                    ⁢                                          π                      8                                                                                                            sin                    ⁢                                          π                      16                                                                                                            -                                          1                                              2                                                                                                                                  cos                    ⁢                                          π                      16                                                                                                                                  -                      cos                                        ⁢                                          π                      8                                                                                                            sin                    ⁢                                                                  3                        ⁢                        π                                            16                                                                                                                                        1                                          2                                                                                                                                  -                      cos                                        ⁢                                          π                      16                                                                                                            cos                    ⁢                                          π                      8                                                                                                                                  -                      cos                                        ⁢                                                                  3                        ⁢                        π                                            16                                                                                                            1                                          2                                                                                                                                  -                      sin                                        ⁢                                                                  3                        ⁢                        π                                            16                                                                                                            sin                    ⁢                                          π                      8                                                                                                                                  -                      sin                                        ⁢                                          π                      16                                                                                            ]                                              (        2        )            In H.264/AVC standard, N=4 or 8, and their coefficients of transform matrices are as shown in the following equations (3) and (4):
                              D                      4            ×            4                    T                =                  [                                                    1                                            1                                            1                                                              1                  /                  2                                                                                    1                                                              1                  /                  2                                                                              -                  1                                                                              -                  1                                                                                    1                                                                                  -                    1                                    /                  2                                                                              -                  1                                                            1                                                                    1                                                              -                  1                                                            1                                                                                  -                    1                                    /                  2                                                              ]                                    (        3        )                                          D                      8            ×            8                    T                =                  [                                                    8                                            12                                            8                                            10                                            8                                            6                                            4                                            3                                                                    8                                            10                                            4                                                              -                  3                                                                              -                  8                                                                              -                  12                                                                              -                  8                                                                              -                  6                                                                                    8                                            6                                                              -                  4                                                                              -                  12                                                                              -                  8                                                            3                                            8                                            10                                                                    8                                            3                                                              -                  8                                                                              -                  6                                                            8                                            10                                                              -                  4                                                                              -                  12                                                                                    8                                                              -                  3                                                                              -                  8                                                            6                                            8                                                              -                  10                                                                              -                  4                                                            12                                                                    8                                                              -                  6                                                                              -                  4                                                            12                                                              -                  8                                                                              -                  3                                                            8                                                              -                  10                                                                                    8                                                              -                  10                                                            4                                            3                                                              -                  8                                                            12                                                              -                  8                                                            6                                                                    8                                                              -                  12                                                            8                                                              -                  10                                                            8                                                              -                  6                                                            4                                                              -                  3                                                              ]                                    (        4        )            FIG. 1a shows a fast computation topology of a 1-D inverse discrete cosine transform proposed by Loeffler et al., wherein, Ci=√{right arrow over (2)} cos(iπ/16), Si=√{right arrow over (2)} sin(iπ/16), and α=√{right arrow over (2)}. The 1-D inverse discrete cosine transform topology proposed by Loeffler et al. requires 11 multiplications and 29 additions, and this topology is presently the fast computation method utilizing the minimum amount of multiplications. FIGS. 1b and 1c display respectively 4-point and 8-point 1-D inverse integer transform topologies. The conventional 2-D inverse transform requires N2 coefficients, that can be decomposed into row operations of N-point 1-D inverse transform, and column operations of N-point 1-D inverse transform. As depicted in FIGS. 2a and 2b, in a conventional 4×4-point inverse transform, when N=4, a 2-D inverse transform can be decomposed into 4 row operations and 4 column operations, and each operation is a 4-point 1-D inverse transform, so that in a block with a smaller End-Of-Block (EOB) point (namely, the position of the last non-zero coefficient of frequency-domain coefficients), that would require more unnecessary zero-value operations, and such unnecessary computational complexity must be reduced.
Therefore, presently, the performance of inverse transform computation in this respect is not quite satisfactory, and it has much room for improvement.